package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 2478. 完美分割的方案数
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/22 14:55
 */
public class BeautifulPartitions {

    public static void main(String[] args) {
        BeautifulPartitions test = new BeautifulPartitions();

        // 3
        String str = "23542185131";
        int k = 3;
        int minLength = 2;

        // 1
//        String str = "23542185131";
//        int k = 3;
//        int minLength = 3;

        // 1
//        String str = "3312958";
//        int k = 3;
//        int minLength = 1;

        // 4
//        String str = "783938233588472343879134266968";
//        int k = 4;
//        int minLength = 6;

        //
//        String str = Utils.getStr(1000, '1', '9');
//        char[] chars = str.toCharArray();
//        chars[0] = '2';
//        chars[chars.length - 1] = '8';
//        str = String.valueOf(chars);
//        int k = 3;
//        int minLength = 1;
//        System.out.println();
//        System.out.println("\"" + str + "\"");
//        System.out.println(k);
//        System.out.println(minLength);
//        System.out.println();

        int i = test.beautifulPartitions(str, k, minLength);
        System.out.println(i);
    }

    public int beautifulPartitions(String s, int k, int minLength) {
        int length = s.length();
        char pre = s.charAt(0);
        char item = s.charAt(length - 1);
        if (pre == '1' || pre == '4' || pre == '6' || pre == '8' || pre == '9'
                || item == '2' || item == '3' || item == '5' || item == '7') {
            return 0;
        }
        long[][] arr = new long[k][length];
        int[] flag = new int[length];
        for (int i = 1; i < length; i++) {
            item = s.charAt(i);
            if ((pre == '1' || pre == '4' || pre == '6' || pre == '8' || pre == '9')
                    && (item == '2' || item == '3' || item == '5' || item == '7')) {
                flag[i - 1] = 1;
            }
            pre = item;
        }
        flag[length - 1] = 1;
        long[] ints = arr[0];
        long[] sums1 = new long[length];
        long[] sums2 = new long[length];
        long t = 0;
        for (int i = minLength - 1; i < length; i++) {
            if (flag[i] == 1) {
                ints[i] = 1;
            }
            sums1[i] = t + ints[i];
            t = sums1[i];
        }
        for (int i = 1; i < k; i++) {
            int st = Math.min((i) * minLength - 2, length - 1);
            long v = st < 0 ? 0 : sums1[st];
            ints = arr[i];
            for (int j = (i + 1) * minLength - 1; j < length; j++) {
                if (flag[j] == 1) {
                    ints[j] = (sums1[j - minLength] - v) % 1000000007;
                }
                sums2[j] = (sums2[j - 1] + ints[j]) % 1000000007;
            }
            System.arraycopy(sums2, 0, sums1, 0, length);
        }
        return (int) (arr[k - 1][length - 1] % 1000000007);
    }

}
